package _04_递归;
/*
    ① 明确函数的功能
     先不要去思考里面代码怎么写，首先搞清楚这个函数的干嘛用的，能完成什么功能？

    ② 明确原问题与子问题的关系
     寻找 f(n) 与 f(n – 1) 的关系,有时候可能是f(n)与f(n-2),f(n-3)的关系

    ③ 明确递归基（边界条件）
     递归的过程中，子问题的规模在不断减小，当小到一定程度时可以直接得出它的解
     寻找递归基，相当于是思考：问题规模小到什么程度可以直接得出解？

    递归调用的空间复杂度 = 递归深度 * 每次调用所需的辅助空间
    递归深度：函数调用最深的那一条线
 */
public class Main {
    public static void main(String[] args) {

    }

    //练习1：斐波那契数列：1、1、2、3、5、8、13、21、34
    //1.函数功能：计算第n项的斐波那契数
    //2.原问题:fib(n) = fib(n-1) + fib(n-2)
    static int fib(int n){
        if(n<=2) return 1;
        return fib(n-1) + fib(n-2);
    }

    //优化，使用滚动数组来计算，每次是用到数组中连续的几个数字，就可以考虑使用滚动数组
    static int fib2(int n){
        if(n<=2) return 1;
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for(int i=3;i<=n;++i){
            array[i&1] = array[(i-1)&1] + array[(i-2)&1];
        }
        return array[n&1];
    }

    //练习2：上楼梯 一次可以走一阶，也可以一次走两阶,走完n阶共有多少种走法？
    //函数功能：返回n个台阶的走法
    static int fn(int n){
        if(n<=2) return 2;
      //一次走一步，一次走两步
        return fn(n-1) + fn(n-2);
    }
}
